This invention relates to an encoder and a decoder for data signals and, more particularly, to entropy encoding and decoding.
Adaptive encoding is a known method of efficiently encoding data signals. An adaptive encoding device encodes a data signal while studying the occurrence probability of the object of encoding or decoding. Therefore, adaptive coding avoids decreased coding efficiency.
An adaptive encoding and de coding device is described in five articles concerning xe2x80x9cQ-coder adaptive binary arithmetic coderxe2x80x9d, and appearing in IBM Journal of Research and Development, Vol. 32, No. 6, Nov. 1998, pp. 717-774. In addition, the principle of an arithmetic coder and decoder having an entropy encoding and decoding means is described in U.S. Pat. No. 5,059,976. FIG. 1 of that patent, reproduced here as FIG. 12, illustrates an example in which the binary symbol 001(sequence length 3) is encoded by an arithmetic coder. That encoding is described in the following paragraphs.
In coding a Markov information source, a number line representation coding system is used. In that system a sequence of symbols is mapped on number lines from 0.00 to 1.0 and having coordinates coded as code words which are, for example, represented in a binary expression. FIG. 12 is a conceptual diagram of the number line representation system. For simplicity, a bi-level memoryless information source is shown. The occurrence probability for xe2x80x9c1xe2x80x9d is set at r and the occurrence probability for xe2x80x9c0xe2x80x9d is set at 1-r. When an output sequence length is set at 3, the coordinates of each of the rightmost C(000) to C(111), represented as a binary expression, is truncated at the digit that allows distinction from the other, and is defined as its respective code word. Decoding is possible at a receiving side by performing the same procedure as at the transmission side.
In such a sequence, the mapping interval Ai, and the lower-end coordinates Ci of the symbol sequence at time i are given as follows:
When the output symbol ai is 0 (More Probable Symbol: hereinafter called MPS),
Ai=(1-r)Aixe2x88x921 and
Ci=Cixe2x88x921.
When the output symbol ai is 1 (Less Probable Symbol: hereinafter called LPS),
Ai=rAixe2x88x921 and
Ci=Cixe2x88x921+(1-r)Aixe2x88x921.
As described in xe2x80x9cAn overview of the basic principles of the Q-Coder adaptive binary arithmetic coderxe2x80x9d, IBM Journal of Research and Development, Vol. 32, No. 6, November 1988, pp. 717-736, in order to reduce the number of calculations, such as multiplication, a set of fixed values are prepared and a certain value is selected from among them, not necessarily calculating rAixe2x88x921.
That is, if rAixe2x88x921 of the foregoing expression is set at S,
when ai=0,
Ai=Aixe2x88x921xe2x88x92S
Ci=Cixe2x88x921 
when ai=1,
Ai=S
Ci=Cixe2x88x921+(Aixe2x88x921xe2x88x92S)
However, as Aixe2x88x921 becomes successively smaller, S also needs to be smaller, in this instance. To maintain calculation accuracy, it is necessary to multiply Aixe2x88x921 by the second power (hereinafter called normalization). In an actual code word, the fixed value is assumed to be the same at all times and is multiplied by powers of xc2xd at the time of calculation (namely, shifted by a bit).
If a constant value is used for S, as described above, a problem arises when, in particular, S is large and a normalized Aixe2x88x921 is relatively small. An example follows.
If Aixe2x88x921 is slightly over 0.5, Ai is very small when ai is an MPS, and is even smaller than the area given when ai is an LPS. That is, in spite of the fact that the occurrence probability of the MPS is high, the area allocated to the MPS is smaller than that allocated to the LPS, leading to an decrease in coding efficiency. If it is assumed that an area allocated to the MPS is always larger than that allocated to the LPS, since Aixe2x88x921 greater than 0.5, S must be 0.25 or smaller. Therefore, when Aixe2x88x921 is 1.0, r=0.25, and when Aixe2x88x921 is close to 0.5, r=0.5, with the result that the occurrence probability of the LPS is considered to vary between xc2xc and xc2xd during coding. If this variation can be made smaller, an area proportional to an occurrence probability can be allocated and an improvement in coding efficiency can be expected.
U.S. Pat. No. 5,025,258 describes a method of calculation of an occurrence probability (Qe) based on the number of times of occurrence. In order to presume the Qe of symbol 1, U.S. Pat. No. 5,059,976 uses learning in the probability estimation means, synchronized with renormalization in the entropy coding means, which is fundamentally independent of the probability estimation means. That is, the adaptability to a change of the information source depends on chance, as indicated in FIG. 13.
Arithmetic coding and decoding are described in the following references:
(1) Langdon et al., xe2x80x9cCompression of Black-White Images with Arithmetic codingxe2x80x9d, IEEE Transactions, Vol. Com-29, No. 6, Jun. 1981, pp. 858-867,
(2) U.S. Pat. No. 4,633,490,
(3) Witten et al., xe2x80x9cArithmetic coding for Data Compressionxe2x80x9d, Communications of the ACM, Vol. 30, No. 6, June 1987, pp. 520-540.
FIG. 11 is a block diagram of an adaptive encoding device and an adaptive decoding device. In FIG. 11, a probability estimation means 30 presumes an occurrence probability of a data value for encoding, and produces a predicted value as a data value with a high occurrence probability. When a multi-value data (not binary data) signal is input, a modeling means 33 analyzes the input signal and classifies it as to context. In the coding device, the modeling means 33 converts the input multi-value data signal into a binary data signal.
In the decoding device, a modeling means 34 analyzes an output signal and classifies it as to context. When a multi-value data (not binary data) signal is output, a modeling means 34 converts the input binary data signal into a multi-value data signal.
In the coding device, a symbol judgment means 38 converts the input data signal into a binary symbol to show agreement or disagreement with the data value for encoding based on the binary data and a predicted value received from a part 36 of a memory as described below. An entropy encoding means 31 encodes the data value output by the symbol judgment means, based on the probability established separately and supplied from the Qe memory 37 described below.
In the decoding device, a data judgment means 39 converts a binary symbol received from an entropy decoding means 32, into binary data based on the binary symbol and a predicted value received from a part 36 of a memory in the decoding device. The entropy decoding is based on the probability separately established and stored in a Qe memory in decoding device.
The structure of FIG. 11 has separate modeling means 33 and modeling means 34 in the encoding and decoding devices. These modeling means may include generally known probability estimation means 30 including data and symbol conversion and inversion function. In the described structure, no conversion and inversion functions in the modeling means 33 and 34 are needed if the modeling means receive binary signals.
A state number is stored into a part 35 of a memory as an index for selecting an estimation probability value (MPS or LPS) for the Qe memory 37. An arithmetic coder and an arithmetic decoder are included in the entropy encoder means 31 and the entropy decoder means 32, respectively. In the encoding device of FIG. 11, the state number memory part 35 receives the context from the modeling means 33. The memory part 36 stores a predicted value 36, based on the context and state number. The Qe memory 37 detects a probability representation value (MPS or LPS). The symbol judgment means 38 produces a binary symbol to establish agreement or disagreement of the data value for encoding based on the binary data and the predicted value. The probability representation value (LPS or MPS) and the binary symbol are sent to the entropy encoding means 31 and the entropy encoding means 31 produces a code in response.
For decoding, the entropy encoding means 31 sends the code to a entropy decoding means 32. The entropy decoding means 32 receives a probability representation value (LPS or MPS) from the Qe memory 37 and the input code. The entropy decoding means 32 produces a binary symbol. A data judgment means 39 receives a predicted value from a part 36 of a memory and the binary symbol from the entropy decoding means 32 and detects binary data based on the binary symbol and the predicted value.
The modeling means 34 receives binary data from the data judgment means 39 and detects a data signal based on the binary data. Moreover, the modeling means 34 converts a multi-value data signal into a binary data signal.
When a multi-value data signal is output, the output data signal is analyzed, and classified as to context, and a multi-value data signal is output. Modeling means 34 converts the binary data signal to decode it. The memory including state number part 35 and predicted value memory part 36 and the Qe memory 37 of the encoding device are the same as on the decoding side. Moreover the memory including parts 35 and 36, the Qe memory 37, symbol judgment means 38, and data judgment means 39 are described in one figure and a flow chart in the articles first mentioned and in TU-T Recommendation T. 82, xe2x80x9cInformation Technology-coded Representation of Picture and Audio information-Progressive Bi-Level Image Compressionxe2x80x9d, pp. 23-45, 1993.
Conventional adaptive probability estimation methods using state transitions have a problem in that the probability estimation performance is not sufficient because learning in the probability estimation means is synchronized with renormalization in the entropy coding means. The entropy coding means is fundamentally independent of the probability estimation means, so the adaptability to a change in the information source depends on chance.
Conventional adaptive probability estimation methods that estimate occurrence probabilities from occurrence counts of data or symbols have a problem in that division to calculate a probability, and multiplication, to sub-divide a numeric line in arithmetic coding, is necessary and causes a heavy operational load.
An object of the present invention is to provide an encoding method and a decoding method that determine an index to select an appropriate coding parameter according to an occurrence probability and producing a smaller operational load.
According to one aspect of the invention, a coding method comprises determining a symbol from an input data signal, setting a threshold for probability values that determine a probability interval corresponding to an index based on an occurrence probability of symbols estimated from occurrence counts of the symbols, determining a probability representation value as a coding parameter using the probability interval of the threshold, and coding the symbol determined from the input data signal, based on the probability representation value.
According to another aspect of the invention, a decoding method comprises setting a threshold for probability values that determine a probability interval corresponding to an index based on occurrence probabilities of symbols estimated from occurrence counts of the symbols, determining a probability representation value as a coding parameter using the probability interval of the threshold, decoding an input code based on the probability representation value and outputting a symbol, and determining output data based on the symbol output in decoding of the input code.
According to yet another aspect of the invention, a probability estimation method includes determining a symbol based on an input data signal, setting a threshold for probability values that determine a probability interval corresponding to an index based on occurrence probabilities of symbols estimated from occurrence counts of the symbols, determining the probability representation value for a calculation parameter using the probability interval of the threshold, and outputting the probability representation value.